Graph

Graph Representation Learning

Graph, Graph Representation Learning

本文是一篇关于Graph Representation Learning的综述。网络特征学习（network representation learning / network embedding）是近年来兴起的一个特征学习的研究分支。作为一种降维方法，网络特征学习试图将一个网络中的节点或者边映射到一个低维连续向量空间中，并在该低维空间中保持原有网络的结构信息，以辅助后续的连接预测、节点分类、推荐系统、聚类、可视化等任务。

Definition

首先简单介绍一下 Graph Representation Learning 的定义，中文可以称之为图特征学习或者网络特征学习。其主要目的在于，将图中每一个节点都映射到一个低维向量空间，并且在此空间内保持原有图的结构信息或距离信息。

以上并非官方权威定义，Graph Representation Learning 目前没有任何官方定义或名字，它也可以被称作 Network Embedding、Graph Embedding 或 GRL。

我们来看上图中的简单例子，左图有三个节点和三条边，其中的数字表示各边的权值 weight，我们通过 GRL 将其映射到一个二维空间中。可以发现，如果两个点之间的 weight 越大，那么它们之间的距离就越近。这就是 GRL 的精髓所在，即在低维空间中保持原有图的结构信息。

Graph Representation Learning 的应用相当广泛，它可以被用于链路预测、 节点分类、推荐系统、视觉、知识图谱表示、聚类、Text Embedding 以及社会网络分析。

Taxonomy

我们将 GRL 的方法按照三种不同分类来进行简单介绍。


首先按输入进行分类，既然是 GRL，那么其输入肯定是一张图，但图的种类有很多：

  1. 第一种叫同构图，即图中的节点和边都只有一种，比如引用网络，其中的节点表示每篇 paper，边表示引用关系。同构图又可以根据是否有加权进行细分，即其边是否权值、边是否有向，以及边是否有正负号。

  2. 第二种是异构图，即网络中的节点和边不止一种，一般分为两种情况：

    • 多媒体网络。比如有的 paper 就考虑过一张图具备图像和文本两种节点，以及图像文本、图像图像和文本文本这三种边。
    • 知识图谱。图中节点表示的是实体，边表示的关系。每一个三元，HRT 都表示头节点 H 和尾节点 T 有关系 R。由于关系 R 可以有很多种，因此 KG 也属于一种异构图。

  3. 第三种是 Graph with side information，side information 即为辅助信息。这种图是指除了边和点之外，节点和边都会带有辅助信息，比如边和点都有 label，边和点都有 attribute，或者 node 有 feature。它们的区别在于 label 是类别型的，attribute 可以是离散的，也可以是连续的，而 feature 就可能是文本或图像等更复杂的一些特征。

  4. 第四种是 Graph Transformed from non-relational data，即从非关系型数据中转换成的图，一般是指在高维空间中的一些数据。这通常是早期 GRL 方法会用到的数据，其中最为典型的例子是稍后还将提到的流形学习，我们可以将这种方法理解为一种降维方法。

按输出内容我们也可以对 GRL 方法进行分类。

  1. 第一种方法会输出 node embedding，即为每个节点输出 embedding，这也是最常见的一种输出。

  2. 第二种方法是输出 edge embedding，即为每个边输出 embedding。这种输出有两种情况，一种是在 KG 里面，我们会为每一个 relation，也就是每条边都有输出。在 link prediction 的应用中，我们也会为每一条边来输出一个特征，并在后续工作中将其作为边的特征来进行一些分类任务。

  3. 第三种方法会输出 sub-graph embedding，也就是子图的 embedding，包括子结构或团体的 embedding。

  4. 第四种是全图的 embedding，即为一个整图来输出 embedding。如果我们对蛋白质、分子这类数量较多的小图进行 embedding，就可以对比两个分子的相似性。

第三种分类方法是按照方法来进行分类。

  1. 第一种方法是基于矩阵分解。一般来说矩阵分解包含奇异值分解和谱分解，谱分解就是我们常说的特征分解，这种方法是比较传统的方法。

  2. 第二种方法是基于随机游走。这种方法盛名在外，我们后面会提到的 Deep Walk 就是基于随机游走的方法。

  3. 第三种方法是基于深度学习。其中包括基于自编码器以及基于卷积神经网络。

  4. 第四种方法是基于一些自定义的损失函数。这其中又包括三种情况，第一种是最大化边重建概率，第二种是最小化基于距离的损失函数，第三种是最小化 margin-based ranking loss，这种方法常见于 KG embedding。

按照时间顺序可将它们分为三类，第一类是传统方法，包含 PCA、LDA、MDS 等降维方法。2000 年左右出现了一批较为经典的方法，包括 ISOMAP 同态映射，LLE 局部线性镶嵌，LE 拉普拉斯特征分解。

Methods

LDA 线性判别分析是一种传统的有监督降维方法。我们可以看到，右图里面有两类点，有正号表示的一类和有负号表示的一类。

我们需要将二维的点映射到一维上去，LDA 的目标在于让这些投影相同类的点在投影过后，同类的点之间距离尽可能变近，即让它们的协方差尽可能小，而不同类的点之间的距离尽可能远。只有这样，它才能在低维空间中对这些点进行分类或聚类操作。


Locally Linear Embedding 是一种典型的流形学习方法，它是指将高维空间中的输入映射到低维空间，并且在低维空间中保持邻居之间的线性依赖关系。

左下图就是一个很典型的流形学习，流形指的是在高维空间中存在某些低维结构，比如说图 A 很像一个瑞士卷，它其实就是一个典型的在三维空间中的二维结构。通过 LLE 我们将其展成一个二维结构。

这种方法的目的在于保持高维空间中的邻居信息。其具体做法如下：对于每一个点 Xi，首先需要确定其邻居集合，然后再来计算 Wik Wij 这些参数。这些参数的意思是，我想用这些邻居来重新构建 Xi，这个会有唯一的解析解。在拿到 W 参数之后，我们再在低维空间中用 W 进行约束，学习得到低维的一个 embedding。


Word2vec 的本质其实是 word embedding，不是 network embedding。但由于它对后续的 network embedding 方法影响深远，所以我们来简单介绍一下。

Word2vec 中有一个 skip-gram 模型，这个模型的本质在于为每个词得到一个特征，并用这个特征来预测周围的词。因此，其具体方法就是将概率最大化。这个概率是指，给定一个中心词 WT，在以它为中心、窗口为 T 的范围中的每个词的概率。

这个概率实际上是使用 softmax 进行计算的。由于 softmax 开销很大，我们通常会用 negative sampling 来进行代替。negative sampling 是指为每个词从整个词表中选择一些 negative samples，把他们作为负样本。


Word2vec 在 Nerwork Embedding 中有两篇很典型的工作，分别是 DeepWalk和 Node2vec。这两篇工作分别发表于 KDD 14 和 KDD 16。DeepWalk 相当于 random walk + word2vec。从图中的每个节点出发，随机进行 random walk，从当前节点均匀、随机地选择下一个节点，然后再从下个节点均匀、随机地选择下一个节点。这样重复 N 次之后会得到一个 path，这个 path 就可以被当做一个 sentence。这样一来，就将问题完全转换到了 Word2vec 的领域。

Node2vec 在 DeepWalk 的基础上又做了改进。它把原来的 random walk 改成了 biased random walk。在 DeepWalk 里，我们是均匀地选择下一个节点。但在 Node2vec 里，则是不均匀地选择下一个节点。我们可以选择模仿 DFS 不断往图的深处走, 也可以模仿 BFS 绕着一个点打转。因此，Node2vec 相比 DeepWalk 也就是新增了一个简单改进。


LINE 的全称是 Large-scale Network Information Embedding。这篇文章发表于 WWW 15。这个工作属于我们之前提到的自定义损失函数，因为它定义了两种损失函数，一种是一阶的临近关系，另一种是二级临近关系。

所谓的一阶临近关系就是指两个点之间是否只有相连。在右图中我们可以看到，点六和点七之间有边相连，那就可以认为它们拥有一阶临近关系。

二阶关系是指两个点的邻居的相似度。右图中点五和点六虽然没有直接相连，但它们的邻居是完全重合的，因此可以认为点五和点六的二阶临近关系很强。基于这样一种临近关系，LINE 定义了两个损失函数 O1 和 O2，然后基于这两个损失函数来进行 network embedding 的学习。


TransX 表示一系列方法，X 可以指代任何字母，这些方法都是基于 KG embedding。KG embedding 是指将 KG 中的每个 entity 和 relation 都映射到一个低维连续空间中，并且保持原来的图结构信息。比较经典的方法有 TransE、TransH 和 TransR，统称为基于翻译的方法。TransE 思路很简单，就是强制让 Head Embedding + relation embedding = tail embedding。换而言之，也就是把 head 加 relation 给翻译成 tail。


SDNE，全名为 Structured Deep Network Embedding。这篇文章发表于 KDD 15，其本质就是基于 auto encoder 的一种 network embedding。

尽管右图看着比较复杂，其实它的思路非常简单。作者设计了一个 auto encoder，其输入是每个点的邻接向量。损失一共有三项，第一项是重建损失，第二项是 proximity loss term，意思是如果两个节点有边连接，那它们的 embedding 必须尽量接近，具体接近程度取决于它们的权重。weight 越大，那么对这项损失的惩罚力度就越大。第三项是正则化项。

GCN[Semi-supervised classification with graph convolutional networks]的定义如下：

这个公式中：

  • $\widetilde{A}=A+I$，$I$是单位矩阵，$A$是邻接矩阵（可以是无向图、有向图、带权图）。只使用A的话，由于A的对角线上都是0，所以在和特征矩阵H相乘的时候，只会计算一个node的所有邻居的特征的加权和，该node自己的特征却被忽略了。因此，给A加上一个单位矩阵I，这样就让对角线元素变成1了。
  • $\widetilde{D}$是$\widetilde{A}$的度矩阵（degree matrix），公式为 $\widetilde{D}_{ii}=\sum _{j} \widetilde{A}_{ij}$
  • $H^{(l)}$是第l层的特征，对于输入层的话，H就是所有节点的初始特征矩阵X，N×D维（N为节点数，D为节点特征维数）
  • σ是非线性激活函数

上图中的GCN输入一个图，通过若干层GCN每个node的特征从X变成了Z，但是，无论中间有多少层，node之间的连接关系，即A都是共享的。假设我们构造一个两层的GCN，激活函数分别采用ReLU和Softmax，则整体的正向传播的公式为：

最后，我们针对所有带标签的节点计算cross entropy损失函数：

由于即使只有很少的node有标签也能训练，作者称他们的方法为半监督分类。_不同的GCN传播算法稍有差异，但本质上都是从邻居节点聚合信息以及上一层的自身表示来更新当前节点的表示。_

metapath2vec：图表征算法deepwalk, node2vec, line等大多数都是针对同构网络的，忽略了网络的异质性，只考虑一种节点对象中的一种关系。然而，现实生活中更多存在的网络是包含不多种类的节点以及连接。比如在DBLP网络，节点种类有会议，论文，作者等，而不同种类节点之间的连接也代表着不同语义，比如说论文和论文之间存在着引用和被引用关系，作者和作者存在合著关系，论文和会议存在发表／被发表关系。因此相比于同构网络，异构网络融合了更多信息，以及包含更丰富的语义信息。所以作者提出了两个在异构网络做network embedding的算法模型，metapath2vec以及metapath2vec++。随机游走从局部上一定程度保持了节点与它邻居之间的连接性，即网络结构信息，然而对于异构信息网络来说，由于节点与连接的异质性的存在，所以异构network embedding最大的难点在于如何有效地在多种类型节点之间保存“节点上下文”的概念。论文提出的想法是：基于预先指定的元路径来进行随机游走，构造路径，从而能够保持“节点上下文”的概念。

这样一来就可以产生一条在不同类型的节点之间且能同时捕捉到网络结构信息以及语义的路径。在得到随机游走路径后，就可以进行skip-gram的建模。论文提出了两种算法：metapath2vec以及metapath2vec++，它们唯一的不同是skip-gram不同。在metapath2vec中，softmax值是在所有节点无论什么类型上进行归一化；而在metapath2vec++中，softmax值是在相同类型节点上进行归一化。

softmax in metapath2vec:

softmax in metapath2vec++:

GATNE-T, GATNE-I

  1. KDD 2019，论文链接

  2. 在阿里电商场景下，由用户和商品构成的图是异构的，不仅包含异构的节点（用户和商品），而且包含异构的边（用户和商品的多种交互行为，比如点击、购买等）。不仅如此，图中的节点还包含着丰富的属性。本文处理的就是这种包含异构节点和异构边的图的表示学习。下图是一个带节点属性的异构图的例子。在左侧原始的图中，用户包含了性别、年龄等属性，商品包含了价格、类目等属性。用户与商品之间包含了4种类型的边，分别对应点击、收藏、加入购物车以及购买行为。

    传统的graph embedding算法比如DeepWalk的做法会忽略图中边的类型以及节点的特征，然后转换成一个HON。如果将边的类型考虑进去，那么就得到一个MHEN，能够取得非常明显的效果。此外，如果将节点的属性也同时考虑进去，那么就利用了原图的所有信息，可以得到最好的效果。下图是作者对目前已有的图表征方法做的总结：

  3. 模型：由于有多种类型的边(比如点击、购买)，论文认为每个节点在每种边类型下都需要学习一个表示。比如给用户和商品在点击场景下学一种表示，在购买场景下学一种表示。但是这两种表示之间并不是完全独立的，是通过某种机制互相影响的。本文主要考虑的就是如何来建模不同类型的表示之间相互影响的方式。对于GATNE-T(T for transductive)来说，每个节点在每种edge type下的embedding由两个部分组成，分别是base embedding和edge embedding。base embedding是每个节点在每种edge type下共享的，而edge embedding是通过相邻节点的edge embedding计算得到的。由于实际问题中会遇到冷启动等问题，需要给没有在训练集中出现过的节点也求得embedding。而transductive model不具备这种能力。所以引入了节点的特征提出了相应的inductive model，记为GATNE-I。具体来说，原先在GATNE-T中和都是随机初始化的。但是在GATNE-I，这两个embedding都是基于节点的特征，也就是通过节点的特征经过某种变换(比如线性变换或者神经网络等)得到的。GATNE-T/I模型的训练方式基于meta-path-based random walk和heterogeneous skip gram。

    Reference

Share